package main.链表;

import common.ListNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.Stack;

/**
 * @author tmh
 * @date 2024/7/26 19:03
 * @description
 */
public class T24两两交换链表中的节点 {
    public static void main(String[] args) {
        ListNode head  =new ListNode(1);
        head.next=new ListNode(2);
        head.next.next=new ListNode(3);
        head.next.next.next=new ListNode(4);
        swapPairs(head);
    }
    /**
     * 使用栈来实现节点的交换操作
     *
     * @param head
     * @return
     */
    public static ListNode swapPairs(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        Deque<ListNode> deque = new ArrayDeque<>();
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while (head != null && head.next != null) {
            deque.addFirst(head);
            deque.addFirst(head.next);
            //把节点加入栈之后就移动head，不然会有其他错误产生，比如死循环
            head = head.next.next;
            dummy.next = deque.removeFirst();
            dummy = dummy.next;
            dummy.next = deque.removeFirst();
            dummy=dummy.next;
        }
        //注意边界条件，当链表长度是奇数时，cur就不为空
        if (head!=null){
            dummy.next=head;
        }else {
            //如果不加这个条件就会产生循环依赖的问题，踩过坑坑
            dummy.next=null;
        }
        return p.next;
    }
}
